/*
Source : https://leetcode.com/problems/integer-to-english-words/
Author : nflush@outlook.com
Date   : 2016-07-18
*/
/*
273. Integer to English Words
 ?  

Question Editorial Solution  
 My Submissions 




?Total Accepted: 18296
?Total Submissions: 93928
?Difficulty: Hard



Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1. 

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"


Hint:
1.Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.Show More Hint ?
*/

class Solution {
private:
    string numberToWordsIn(const int num){
        const string a[] = {
            "Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety","Hundred"
        };
        const string b[] = {
            "Zero","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"
        };
        int h = num / 100;
        int x = num % 100;
        string res;
        if (h > 0){
            if (x > 0){
                res = b[h] + " Hundred ";
            } else {
                res = b[h] + " Hundred";
            }
        }
        if (x > 0){
            if (x < 20){
                res += b[x];
            } else {
                if (x%10)
                    res += a[(x / 10) - 2] + " " + b[x%10];
                else
                    res += a[(x / 10) - 2];
            }
        }
        return res;
    }
public:
    string numberToWords(int num) {
        if (0 == num) return "Zero";
        int b = num / 1000000000;
        int m = (num % 1000000000)/1000000;
        int t = (num % 1000000) / 1000;
        int x = num % 1000;
        string res;
        if (b > 0){
            if (m > 0 || t > 0 || x > 0)
                res = numberToWordsIn(b) + " Billion ";
            else
                res = numberToWordsIn(b) + " Billion";
        }
        if (m > 0){
            if (t > 0 || x > 0)
                res += numberToWordsIn(m) + " Million ";
            else
                res += numberToWordsIn(m) + " Million";
        }
        if (t > 0){
            if (x)
                res += numberToWordsIn(t) + " Thousand ";
            else
                res += numberToWordsIn(t) + " Thousand";
        }
        if (x > 0){
            res += numberToWordsIn(x);
        }
        return res;
    }
};
